package com.whiteseason.sortdemo;

import java.util.LinkedList;

/**
 * 快速排序
 */
public class LinkQuickSort {
    public LinkedList<Integer> count(LinkedList<Integer> arr){
        if (arr.size() < 2){
            return arr;
        }
        LinkedList<Integer> left = new LinkedList<>();
        LinkedList<Integer> right = new LinkedList<>();
        Integer index = arr.pollFirst();
        int size = arr.size();
        for (int i = 0; i < size; i++) {
            Integer temp = arr.poll();
            assert temp != null;
            if (temp < index){
                left.add(temp);
            }else{
                right.add(temp);
            }
        }
        if (left.size() > 1)
            left = count(left);
        if (right.size() > 1)
            right = count(right);
        left.add(index);
        left.addAll(right);
        return left;
    }

    public static void main(String[] args) {
        LinkedList<Integer> arr = new LinkedList<Integer>(){
            {
                add(1);
                add(9);
                add(7);
                add(4);
                add(2);
                add(5);
                add(10);
                add(8);
                add(11);
                add(2);
                add(45);
                add(21);
            }
        };

        arr = new LinkQuickSort().count(arr);
        while (arr.size() != 0)
            System.out.println(arr.pollFirst());
    }
}
